package com.lzq.leetcode.lanqiao.th12;

public class s4 {

    private static int N = 8;
    private static int M = (int)Math.pow(2, N);

    public static void main(String[] args) {

        // 初始计算状态
        boolean[] status = new boolean[M];
        for (int i=0; i<M; i++) {
            status[i] = true;
            int sum = 0;
            for (int j=0; j<N; j++) {
                if ( ((i >> j) & 1) == 0 ) {
                    ++sum;
                } else {
                    if (sum%2 == 1) {
                        // 不可行
                        status[i] = false;
                        break;
                    } else {
                        sum = 0;
                    }
                }

            }
            if (sum%2 == 1) status[i] = false;
        }
        // 计算dp
        int[][] dp = new int[N][M];
        // 初始化第一行
        for (int i=0; i<M; i++) {
            if (status[i])  dp[0][i] = 1;
        }
        // 遍历其他
        for (int i=1; i<N; i++) {
            for (int j=0; j<M; j++) {
                for (int ps=0; ps<M; ps++) {
                    if ( (ps & j) == 0) {
                        // 不同时伸出去, 那就是允许状态
                        // 还需要判断这个状态是否能够被竖向方块完全填充
                        if (status[j|ps]) {
                            dp[i][j] += dp[i-1][ps];
                        }
                    }
                }

            }
        }

        System.out.println(dp[N-1][0]);
    }
}
